НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №3 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «Методи сортування» Варіант № 20 Дата «16» травня 2022  Мета роботи: Метою лабораторної роботи є набуття практичних навичок з використання простих методів сортування. Завдання до лабораторної роботи: Розробити програму з алгоритмом згідно варіанту з використанням методів сортування. Оцінити час виконання та складність алгоритму. 1. Провести сортування масивів вказаним методом та у вказаному порядку. Для тестування алгоритмів сортування масив (10x10, та більше бажанням). 2. Самостійно обрати додатковий метод та провести сортування того ж масиву. 3. Порівняти кількість перестановок (або час виконання) обох методів. Спробувати порівняти час виконання сортування з масивом більшого розміру, який створити за допомогою генератора випадкових чисел. Завдання для варіанту 20: Метод сортування вставками / Теоретичні відомості Алгоритми сортування - це методи реорганізації великої кількості елементів у певний порядок, наприклад, від найвищого до найнижчого, або навпаки, або навіть в якомусь алфавітному порядку. Ці алгоритми беруть вхідний список, обробляють його (тобто виконують над ним деякі операції) і створюють відсортований список. Найпоширеніший приклад, з яким ми стикаємось щодня - це сортування одягу чи інших предметів на веб-сайті електронної комерції або за найнижчою ціною, або за списком за популярністю, або за іншим замовленням. Типи сортувальних алгоритмів: Quick Sort Bubble Sort Merge Sort Insertion Sort Selection Sort Heap Sort Radix Sort Bucket Sort Порівняння алгоритмів: Algorithm Best Average Worst  Quick Sort Ω(n log(n)) Θ(n log(n)) O(n^2)  Bubble Sort Ω(n) Θ(n^2) O(n^2)  Merge Sort Ω(n log(n)) Θ(n log(n)) O(n log(n))  Insertion Sort Ω(n) Θ(n^2) O(n^2)  Selection Sort Ω(n^2) Θ(n^2) O(n^2)  Heap Sort Ω(n log(n)) Θ(n log(n)) O(n log(n))  Radix Sort Ω(nk) Θ(nk) O(nk)  Bucket Sort Ω(n+k) Θ(n+k) O(n^2)   Виконання роботи Порівняння часу виконання в залежності від розміру масиву Розмір масиву Кількість ітерацій Час виконання    Insertion sort Bubble sort  10x10 110 0.149ms 0.248ms  26x26 1118 0.465ms 1.207ms   / Результати Для масиву розмірністю 10 на 10: / Для масиву розмірністю 26 на 26: / / Висновки: У ході виконання даної лабораторної роботи було отримано практичні навички з використання простих методів сортування. Порівняно час роботи та кількість ітерацій програми з різною розмірністю масиву використовуючи різні методи сортування.  Код програми у вигляді скріншотів Метод сортування вставками / Бульбашкове сортування / Час виконання /